The present invention relates generally to data processing systems and, more particularly, to the generation of belief networks.
The advent of artificial intelligence within computer science has brought an abundance of decision-support systems. Decision-support systems are computer systems in which decisions, typically rendered by humans, are recommended and sometimes made. In creating decision-support systems, computer scientists seek to provide decisions with as high of a level of accuracy as possible. Thus, computer scientists strive to create decision-support systems that are equivalent to or more accurate than a human expert Applications of decision-support systems include medical diagnosis, troubleshooting computer networks, or other systems wherein a decision is based upon identifiable criteria.
One of the most promising new areas for research in decision-support systems is belief networks. A belief network is a representation of the probabilistic relationships among states of a portion of the world. The states of the world in a belief network can change and are, therefore, called variables. A belief network is expressed as an acyclic-directed graph where the variables correspond to nodes and the relationships between the nodes correspond to arcs. FIG. 1 depicts an example belief network 101. In FIG. 1 there are three variables, X1, X2, and X3, which are represented by nodes 102, 106 and 110, respectively. The example belief network contains two arcs 104 and 108. Associated with each variable in a belief network is a set of probability distributions. Using conditional probability notation, the set of probability distributions for a variable can be denoted by p(xi|Πi,"xgr"), where xe2x80x9cpxe2x80x9d refers to the probability distribution, where xe2x80x9cΠixe2x80x9d denotes the parents of variable Xi and where xe2x80x9c"xgr"xe2x80x9d denotes the knowledge of the expert. The Greek letter xe2x80x9c"xgr"xe2x80x9d indicates that the belief network reflects the knowledge of an expert in a given field. Thus, this expression reads as follows: the probability distribution for variable Xi given the parents of Xi and the knowledge of the expert. For example, X1 is the parent of X2. The probability distributions specify the strength of the relationships between variables. For instance, if X1 has two states (true and false), then associated with X1 is a single probability distribution p(x1|"xgr") and associated with X2 are two probability distributions p(x2|x1=t,"xgr") and p(x2|x1=f,"xgr").
The arcs in a belief network convey dependence between nodes. When there is an arc from a first node to a second node, the probability distribution of the first node depends upon the value of the second node when the direction of the arc points from the second node to the first node. For example, node 106 depends upon node 102. Therefore, node 106 is said to be conditionally dependent. Missing arcs in a belief network convey conditional independence. For example, node 102 and node 110 are conditionally independent given node 106. However, two variables indirectly connected through intermediate variables are conditionally dependent given knowledge of the values (xe2x80x9cstatesxe2x80x9d) of the intermediate variables. Therefore, if the value for X2 is known, X1 and X3 are conditionally dependent.
In other words, sets of variables X and Y are said to be conditionally independent, given a set of variables Z, if the probability distribution for X given Z does not depend on Y. If Z is empty, however, X and Y are said to be xe2x80x9cindependentxe2x80x9d as opposed to conditionally independent. If X and Y are not conditionally independent, given Z, X and Y are said to be conditionally dependent.
The variables used for each node may be of different types. Specifically, variables may be of two types: discrete or continuous. A discrete variable is a variable that has a finite number of states, whereas a continuous variable is a variable that has an uncountably infinite number of states. An example of a discrete variable is a Boolean variable. Such a variable can assume only one of two states: xe2x80x9ctruexe2x80x9d or xe2x80x9cfalse.xe2x80x9d An example of a continuous variable is a variable that may assume any real value between xe2x88x921 and 1. Discrete variables have an associated probability distribution. Continuous variables, however, have an associated probability density function (xe2x80x9cdensityxe2x80x9d). Where an event is a set of possible outcomes, the density xcfx81(x) for a variable xe2x80x9cxxe2x80x9d and events xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d is defined as:       ρ    ⁢          (      x      )        =            Lim              a        ->        b              ⁡          [                        ρ          ⁢                      (                          a              ≤              x              ≤              b                        )                                    "LeftBracketingBar"                      (                          a              -              b                        )                    "RightBracketingBar"                    ]      
Where xcfx81(axe2x89xa6xxe2x89xa6b) is the probability that x lies between a and b. Conventional systems for generating belief networks cannot use continuous variables in their nodes.
FIG. 2 depicts an example belief network for troubleshooting automobile problems. The belief network of FIG. 2 contains many variables 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 224, 226, 228, 230, 232, and 234, relating to whether an automobile will work properly and arcs 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 256, 258, 260, 262, 264, 268. A few examples of the relationships between the variables follow. For the radio 214 to work properly, there must be battery power 212 (arc 246). Battery power 212, in turn, depends upon the battery working properly 208 and a charge 210 (arcs 242 and 244). The battery working properly 208 depends upon the battery age 202 (arc 236). The charge 210 of the battery depends upon the alternator 204 working properly (arc 238) and the fan belt 206 being intact (arc 240). The battery age variable 202, whose values lie from zero to infinity, is an example of a continuous variable that can contain an infinite number of values. However, the battery variable 208 reflecting the correct operations of the battery is a discrete variable being either true or false.
The automobile troubleshooting belief network also provides a number of examples of conditional independence and conditional dependence. The nodes operation of the lights 216 and battery power 212 are conditionally dependent, and the nodes operation of the lights 216 and operation of the radio 214 are conditionally independent given operation of the lights 216. However, the operation of the radio 214 and the operation of the lights 216 are conditionally dependent given the battery power 212. The concept of conditional dependence and conditional independence can be expressed using conditional probability notation. For example, the operation of the lights 216 is conditionally dependent on battery power 212 and conditionally independent of the radio 214. Therefore, the probability of the lights working properly 216 given both the battery power 212 and the radio 214 is equivalent to the probability of the lights working properly given the battery power alone, P(Lights|Battery Power, Radio, "xgr")=P(Lights|Battery Power, "xgr"). An example of a conditional dependence relationship is the probability of the lights working properly 216 given the battery power 212 is not equivalent to the probability of the lights working properly given no information. That is, p(Lights|Battery Power, "xgr")xe2x89xa0p(Lights|"xgr").
There are two conventional approaches for constructing belief networks. Using the first approach (xe2x80x9cthe knowledge-based approachxe2x80x9d), a person known as a knowledge engineer interviews an expert in a given field to obtain the knowledge of the expert about the field of expertise of the expert. The knowledge engineer and expert first determine the distinctions of the world that are important for decision making in the field of the expert. These distinctions correspond to the variables of the domain of the belief network. The xe2x80x9cdomainxe2x80x9d of a belief network is the set of all variables in the belief network. The knowledge engineer and the expert next determine the dependencies among the variables (the arcs) and the probability distributions that quantify the strengths of the dependencies.
In the second approach (xe2x80x9ccalled the data-based approachxe2x80x9d), the knowledge engineer and the expert first determine the variables of the domain. Next, data is accumulated for those variables, and an algorithm is applied that creates a belief network from this data. The accumulated data comes from real world instances of the domain. That is, real world instances of decision making in a given field. Conventionally, this second approach exists for domains containing only discrete variables.
After the belief network has been created, the belief network becomes the engine for a decision-support system. The belief network is converted into a computer-readable form, such as a file and input into a computer system. Then, the computer system uses the belief network to determine the probabilities of variable states given observations, determine the benefits of performing tests, and ultimately recommend or render a decision. Consider an example where a decision-support system uses the belief network of FIG. 2 to troubleshoot automobile problems. If the engine for an automobile did not start, the decision-based system could request an observation of whether there was gas 224, whether the fuel pump 226 was in working order by possibly performing a test, whether the fuel line 228 was obstructed, whether the distributor 230 was working, and whether the spark plugs 232 were working. While the observations and tests are being performed, the belief network assists in determining which variable should be observed next.
In accordance with a first aspect of the present invention, a method is executed in a computer system capable of receiving expert data retrieved from an expert in a given field of expertise and empirical data reflecting observations made in the given field of the expert. In accordance with this method of the first aspect of the present invention, the preferred embodiment generates a belief network by receiving the expert data into the computer system, receiving the empirical data into the computer system, and creating a belief network utilizing the received expert data and the received empirical data.